{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Lattice Points Inside a Circle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #hash-table #math #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #哈希表 #数学 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countLatticePoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计圆内格点数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>circles</code> ，其中 <code>circles[i] = [x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub>]</code> 表示网格上圆心为 <code>(x<sub>i</sub>, y<sub>i</sub>)</code> 且半径为 <code>r<sub>i</sub></code> 的第 <code>i</code> 个圆，返回出现在<strong> 至少一个 </strong>圆内的 <strong>格点数目</strong> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>格点</strong> 是指整数坐标对应的点。</li>\n",
    "\t<li><strong>圆周上的点</strong> 也被视为出现在圆内的点。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/02/exa-11.png\" style=\"width: 300px; height: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>circles = [[2,2,1]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "给定的圆如上图所示。\n",
    "出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2)，在图中用绿色标识。\n",
    "像 (1, 1) 和 (1, 3) 这样用红色标识的点，并未出现在圆内。\n",
    "因此，出现在至少一个圆内的格点数目是 5 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/02/exa-22.png\" style=\"width: 300px; height: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>circles = [[2,2,2],[3,4,1]]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>\n",
    "给定的圆如上图所示。\n",
    "共有 16 个格点出现在至少一个圆内。\n",
    "其中部分点的坐标是 (0, 2)、(2, 0)、(2, 4)、(3, 2) 和 (4, 4) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= circles.length &lt;= 200</code></li>\n",
    "\t<li><code>circles[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= r<sub>i</sub> &lt;= min(x<sub>i</sub>, y<sub>i</sub>)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-lattice-points-inside-a-circle](https://leetcode.cn/problems/count-lattice-points-inside-a-circle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-lattice-points-inside-a-circle](https://leetcode.cn/problems/count-lattice-points-inside-a-circle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,2,1]]', '[[2,2,2],[3,4,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        # r = -inf\n",
    "        # u = -inf\n",
    "        circles.sort(key = lambda x:-x[2])\n",
    "        # for x,y,ri in circles:\n",
    "        #     r = max(r,x+ri)\n",
    "        #     u = max(u,y+ri)\n",
    "        r = max(x[0]+x[2] for x in circles)\n",
    "        u = max(x[1]+x[2] for x in circles)\n",
    "        \n",
    "        n = len(circles)\n",
    "        ans = 0\n",
    "        for x in range(0,r+1):\n",
    "            for y in range(0,u+1):\n",
    "                for xi,yi,ri in circles:\n",
    "                    if (x-xi)**2+(y-yi)**2<=ri**2:\n",
    "                        ans+=1\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        circles.sort(key=lambda c: -c[2])  # 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆\n",
    "        max_x = max(c[0] + c[2] for c in circles)\n",
    "        max_y = max(c[1] + c[2] for c in circles)\n",
    "        for i in range(max_x + 1):\n",
    "            for j in range(max_y + 1):\n",
    "                for x, y, r in circles:\n",
    "                    if (x - i) * (x - i) + (y - j) * (y - j) <= r * r:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        circles.sort(key=lambda c: -c[2])  # 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆\n",
    "        max_x = max(c[0] + c[2] for c in circles)\n",
    "        max_y = max(c[1] + c[2] for c in circles)\n",
    "        for i in range(max_x + 1):\n",
    "            for j in range(max_y + 1):\n",
    "                for x, y, r in circles:\n",
    "                    if (x - i) ** 2 + (y - j) ** 2 <= r * r:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        circles.sort(key=lambda c: -c[2])  # 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆\n",
    "        max_x = max(c[0] + c[2] for c in circles)\n",
    "        max_y = max(c[1] + c[2] for c in circles)\n",
    "        for i in range(max_x + 1):\n",
    "            for j in range(max_y + 1):\n",
    "                for x, y, r in circles:\n",
    "                    if (x - i) * (x - i) + (y - j) * (y - j) <= r * r:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        circles.sort(key=lambda c: -c[2])  # 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆\n",
    "\n",
    "        max_x = max(c[0] + c[2] for c in circles)\n",
    "\n",
    "        max_y = max(c[1] + c[2] for c in circles)\n",
    "\n",
    "        for i in range(max_x + 1):\n",
    "\n",
    "            for j in range(max_y + 1):\n",
    "\n",
    "                for x, y, r in circles:\n",
    "\n",
    "                    if (x - i) * (x - i) + (y - j) * (y - j) <= r * r:\n",
    "\n",
    "                        ans += 1\n",
    "\n",
    "                        break\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        mx, my = max(cx + cr for cx, cy, cr in circles) + 2, max(cy + cr for cx, cy, cr in circles) + 1\n",
    "        diffs = [[0] * mx for _ in range(my)]\n",
    "        for cx, cy, cr in circles:\n",
    "            for y in range(cy - cr, cy + cr + 1):\n",
    "                z = isqrt(cr * cr - (y - cy) * (y - cy))\n",
    "                diffs[y][cx - z] += 1\n",
    "                diffs[y][cx + z + 1] -= 1\n",
    "        return sum(sum(cur > 0 for cur in accumulate(xs)) for xs in diffs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        circles.sort(key=lambda c: -c[2])  # 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆\n",
    "        max_x = max(c[0] + c[2] for c in circles)\n",
    "        max_y = max(c[1] + c[2] for c in circles)\n",
    "        for i in range(max_x + 1):\n",
    "            for j in range(max_y + 1):\n",
    "                for x, y, r in circles:\n",
    "                    if (x - i) * (x - i) + (y - j) * (y - j) <= r * r:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        mx, my = max(cx + cr for cx, cy, cr in circles) + 2, max(cy + cr for cx, cy, cr in circles) + 1\n",
    "        diffs = [[0] * mx for _ in range(my)]\n",
    "        for cx, cy, cr in circles:\n",
    "            for y in range(cy - cr, cy + cr + 1):\n",
    "                z = isqrt(cr * cr - (y - cy) * (y - cy))\n",
    "                diffs[y][cx - z] += 1\n",
    "                diffs[y][cx + z + 1] -= 1\n",
    "        return sum(sum(map(bool, accumulate(xs))) for xs in diffs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        mx, my = max(cx + cr for cx, cy, cr in circles) + 2, max(cy + cr for cx, cy, cr in circles) + 1\n",
    "        diffs = [[0] * mx for _ in range(my)]\n",
    "        for cx, cy, cr in circles:\n",
    "            for y in range(cy - cr, cy + cr + 1):\n",
    "                z = isqrt(cr * cr - (y - cy) * (y - cy))\n",
    "                diffs[y][cx - z] += 1\n",
    "                diffs[y][cx + z + 1] -= 1\n",
    "        return sum(sum(map(bool, accumulate(xs))) for xs in diffs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        mx, my = max(cx + cr for cx, cy, cr in circles) + 2, max(cy + cr for cx, cy, cr in circles) + 1\n",
    "        diffs = [[0] * mx for _ in range(my)]\n",
    "        for cx, cy, cr in circles:\n",
    "            for y in range(cy - cr, cy + cr + 1):\n",
    "                z = isqrt(cr * cr - (y - cy) * (y - cy))\n",
    "                diffs[y][cx - z] += 1\n",
    "                diffs[y][cx + z + 1] -= 1\n",
    "        return sum(sum(map(bool, accumulate(xs))) for xs in diffs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        ## 题目给了条件1 <= ri <= min(xi, yi)，所以座标肯定大于等于0\n",
    "        ## 方法一：暴力枚举\n",
    "        ## 其实也可以i和j用0到200枚举，只是可能会超时\n",
    "        # ans = 0\n",
    "        # circles.sort(key = lambda x: -x[2]) ## 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆\n",
    "        # max_x = max(c[0] + c[2] for c in circles)\n",
    "        # max_y = max(c[1] + c[2] for c in circles)\n",
    "        # for i in range(max_x + 1):\n",
    "        #     for j in range(max_y + 1):\n",
    "        #         for x, y, r in circles:\n",
    "        #             if (x - i) * (x - i) + (y - j) * (y - j) <= r * r:\n",
    "        #                 ans += 1\n",
    "        #                 break\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        ## Y的可用范围为[0, maxY + maxR]，X的可用范围为[0, maxX + 1 + maxR]\n",
    "        # 步骤\n",
    "        # 求出X、Y的最大最小值和半径R的最大值；\n",
    "        # 构造差分数组diff，每个Y一个差分数组，Y的可用范围为[0, maxY + maxR]，\n",
    "        # 每个差分数组的范围为[0, maxX + 1 + maxR]；\n",
    "        # 遍历每个圆，再遍历圆心到横线的高度得到len，分别采用差分数组来统计每个点被圆覆盖的次数；\n",
    "        # 遍历差分数组，统计被圆覆盖的点的个数并返回\n",
    "        # 针对每个 y，首先计算出它包含的 “线段” 的左、右端点 (x_1, x_2)(x 1 ,x 2 )，\n",
    "        # 则可以对[x_1, x_2][x 1,x 2 ]范围内的值都加1，表示被1个圆覆盖，\n",
    "        # 如果一个点被多个圆覆盖，则这个值就大于1，不被覆盖则等于0。\n",
    "        mx = max(cx + cr for cx, cy, cr in circles) + 2\n",
    "        my = max(cy + cr for cx, cy, cr in circles) + 1\n",
    "        diffs = [[0] * mx for _ in range(my)]\n",
    "        for cx, cy, cr in circles:\n",
    "            for y in range(cy - cr, cy + cr + 1):\n",
    "                z = isqrt(cr * cr - (y - cy) ** 2)\n",
    "                diffs[y][cx - z] += 1\n",
    "                diffs[y][cx + z + 1] -= 1\n",
    "        return sum(sum(cur > 0 for cur in accumulate(xs)) for xs in diffs)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        records = [[0 for i in range(-100, 400)] for j in range(-100, 400)]\n",
    "        \n",
    "        for circle in circles:\n",
    "            left = circle[0] - circle[2]\n",
    "            right = circle[0] + circle[2]\n",
    "            \n",
    "            up = circle[1] + circle[2]\n",
    "            buttom = circle[1] - circle[2]\n",
    "\n",
    "            for i in range(left, right+1):\n",
    "                for j in range(buttom, up+1):\n",
    "                    if (i - circle[0]) ** 2 + (j - circle[1]) ** 2 <= circle[2] ** 2:\n",
    "                        records[i][j] = 1\n",
    "        \n",
    "        return sum(sum(record) for record in records)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        size=0\n",
    "        for x,y,r in circles:\n",
    "            size=max(size,x+r,y+r)\n",
    "        vis=[[0]*(size+1) for _ in range(size+1)]\n",
    "        for x,y,r in circles:\n",
    "            for dx in range(r+1):\n",
    "                t=r*r-dx*dx\n",
    "                for dy in range(floor(sqrt(t))+1):\n",
    "                    vis[x+dx][y+dy]=1\n",
    "                    vis[x+dx][y-dy]=1\n",
    "                    vis[x-dx][y+dy]=1\n",
    "                    vis[x-dx][y-dy]=1\n",
    "        return sum(sum(g) for g in vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        ##圆内含条件:圆心距离d<=大r-小r\n",
    "        circles.sort(key=lambda x:-x[2])\n",
    "        bigCycle=SortedList()\n",
    "        for x,y,r in circles:\n",
    "            for index in range(len(bigCycle)):\n",
    "                k,i,j=bigCycle[index]\n",
    "                k=-k\n",
    "                if (x-i)*(x-i)+(y-j)*(y-j)<=(r-k)*(r-k):\n",
    "                    break\n",
    "            else:\n",
    "                bigCycle.add((-r,x,y))\n",
    "\n",
    "        size=0\n",
    "        for r,x,y in bigCycle:\n",
    "            size=max(size,x-r,y-r)\n",
    "        vis=[[0]*(size+1) for _ in range(size+1)]\n",
    "        for r,x,y in bigCycle:\n",
    "            r=-r\n",
    "            for dx in range(r+1):\n",
    "                t=r*r-dx*dx\n",
    "                for dy in range(floor(sqrt(t))+1):\n",
    "                    vis[x+dx][y+dy]=1\n",
    "                    vis[x+dx][y-dy]=1\n",
    "                    vis[x-dx][y+dy]=1\n",
    "                    vis[x-dx][y-dy]=1\n",
    "        return sum(sum(g) for g in vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        # 水平扫描线+垂直差分+四边界\n",
    "        lx, hx = float(\"inf\"), -float(\"inf\")\n",
    "        ly, hy = float(\"inf\"), -float(\"inf\")\n",
    "        d = {}\n",
    "        for cx, cy, cr in circles:\n",
    "            lx = min(lx, cx - cr)\n",
    "            hx = max(hx, cx + cr)\n",
    "            ly = min(ly, cy - cr)\n",
    "            hy = max(hy, cy + cr)\n",
    "            for x in range(cx - cr, cx + cr + 1):\n",
    "                # 针对当前圆内的每个x, 更新其y坐标的差分数组\n",
    "                if x not in d:\n",
    "                    d[x] = collections.defaultdict(int)\n",
    "                other = math.sqrt(cr * cr - (x - cx) * (x - cx))\n",
    "                # 当前y的上下界, 注意都取floor, 保证两边界都在圆上或圆内\n",
    "                chy = cy + math.floor(other)\n",
    "                cly = cy - math.floor(other)\n",
    "                d[x][cly] += 1\n",
    "                # 注意上界+1才减去\n",
    "                d[x][chy + 1] -= 1\n",
    "        res = 0\n",
    "        for x in range(lx, hx + 1):\n",
    "            sm = 0\n",
    "            for y in range(ly, hy + 1):\n",
    "                sm += d[x][y]\n",
    "                if sm > 0:\n",
    "                    # 说明当前点在圆上\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        lx, rx = float('inf'), -float('inf')\n",
    "        dy, uy = float('inf'), -float('inf')\n",
    "        d = {}\n",
    "        for cx, cy, cr in circles:\n",
    "            l, r = cx-cr, cx+cr\n",
    "            lx = min(lx, l)\n",
    "            rx = max(rx, r)\n",
    "            dy = min(dy, cy-cr)\n",
    "            uy = max(uy, cy+cr)\n",
    "            for x in range(l, r+1):\n",
    "                if x not in d:\n",
    "                    d[x] = collections.defaultdict(int)\n",
    "                other = math.sqrt(cr*cr-(x-cx)*(x-cx))\n",
    "                hi = cy+math.floor(other)\n",
    "                lo = cy-math.floor(other)\n",
    "                d[x][lo]+=1\n",
    "                d[x][hi+1]-=1\n",
    "        res = 0\n",
    "        for x in range(lx, rx+1):\n",
    "            sm = 0\n",
    "            for y in range(dy, uy+1):\n",
    "                sm += d[x][y]\n",
    "                if sm > 0:\n",
    "                    res+=1\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        def in_circle(tup, circle):\n",
    "            if pow(tup[0] - circle[0], 2) + pow(tup[1] - circle[1], 2) <= pow(circle[2], 2):\n",
    "                return True\n",
    "        count = 0\n",
    "        dots = []\n",
    "        circles.sort(key=lambda x: x[2], reverse=True)\n",
    "        x_list = list(map(lambda x:x[0], circles))        \n",
    "        y_list = list(map(lambda x:x[1], circles))\n",
    "\n",
    "        max_x = max(x_list)       \n",
    "        max_y = max(y_list)\n",
    "        max_r = max(list(map(lambda x:x[2], circles)))\n",
    "        # min_x = min(x_list)       \n",
    "        # min_y = min(y_list)\n",
    "        max_limit_x = max_x + max_r + 1\n",
    "        max_limit_y = max_y + max_r + 1\n",
    "        # min_limit_x = min_x - max_r - 1\n",
    "        # min_limit_y = min_y - max_r - 1\n",
    "\n",
    "        \n",
    "        for i in range(max_limit_x):\n",
    "            for j in range(max_limit_y):\n",
    "                dots.append((i, j))\n",
    "        \n",
    "        for dot in dots:\n",
    "            for circle in circles:\n",
    "                if in_circle(dot, circle):\n",
    "                    count += 1\n",
    "                    break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        n=len(circles)\n",
    "        circles1=[]\n",
    "        for i in range(n):\n",
    "            if circles[i] not in circles1:\n",
    "                circles1.append(circles[i])\n",
    "        circles=circles1     \n",
    "        k=len(circles)\n",
    "     #   print(circles)\n",
    "        ans=[]\n",
    "        l=float(\"+inf\")\n",
    "        r=float(\"-inf\")\n",
    "        u=float(\"-inf\")\n",
    "        d=float(\"+inf\")\n",
    "        for i in range(k):\n",
    "            l=min(circles[i][0]-circles[i][2],l)\n",
    "            r=max(circles[i][0]+circles[i][2],r)\n",
    "            u=max(circles[i][1]+circles[i][2],u)\n",
    "            d=min(circles[i][1]-circles[i][2],d)\n",
    "      #  print(l,r,u,d)\n",
    "        for m in range(l,r+1):\n",
    "            for n in range(d,u+1):\n",
    "                for i in range(k):\n",
    "                    if (m-circles[i][0])**2+(n-circles[i][1])**2<=circles[i][2]**2:\n",
    "                        ans.append([m,n])\n",
    "                        break\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        n=len(circles)\n",
    "        circles1=[]\n",
    "        for i in range(n):\n",
    "            if circles[i] not in circles1:\n",
    "                circles1.append(circles[i])\n",
    "        circles=circles1     \n",
    "        k=len(circles)\n",
    "     #   print(circles)\n",
    "        ans=[]\n",
    "        l=float(\"+inf\")\n",
    "        r=float(\"-inf\")\n",
    "        u=float(\"-inf\")\n",
    "        d=float(\"+inf\")\n",
    "        for i in range(k):\n",
    "            l=min(circles[i][0]-circles[i][2],l)\n",
    "            r=max(circles[i][0]+circles[i][2],r)\n",
    "            u=max(circles[i][1]+circles[i][2],u)\n",
    "            d=min(circles[i][1]-circles[i][2],d)\n",
    "      #  print(l,r,u,d)\n",
    "        for m in range(l,r+1):\n",
    "            for n in range(d,u+1):\n",
    "                for i in range(k):\n",
    "                    if (m-circles[i][0])**2+(n-circles[i][1])**2<=circles[i][2]**2:\n",
    "                        ans.append([m,n])\n",
    "                        break\n",
    "        return len(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        \n",
    "        data = {}\n",
    "        for x, y, r in circles:\n",
    "            for di in range(- r, r + 1):\n",
    "                dj = (r ** 2 - di ** 2) ** (1/2)\n",
    "                dj = math.floor(dj)\n",
    "\n",
    "                if (x + di) not in data:\n",
    "                    data[x + di] = []\n",
    "\n",
    "                data[x + di].append([y - dj, y + dj])\n",
    "\n",
    "        ans = 0\n",
    "        for idx, block_list in data.items():\n",
    "            block_list = sorted(block_list, key=lambda x: x[0])\n",
    "            # print(idx, block_list)\n",
    "        \n",
    "            last_x, last_y = block_list[0]\n",
    "            for x, y in block_list[1:]:\n",
    "                if x <= last_y:\n",
    "                    last_y = max(last_y, y)\n",
    "                else:\n",
    "                    print(idx, last_x, last_y)\n",
    "                    ans += (last_y - last_x + 1)\n",
    "                    last_x, last_y = x, y\n",
    "\n",
    "            print(idx, last_x, last_y)\n",
    "            ans += (last_y - last_x + 1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        \n",
    "        def helper(tx,ty):\n",
    "            for i in range(len(circles)):\n",
    "                x, y, r = circles[i]\n",
    "                if (tx-x)**2 + (ty-y)**2 <= r**2:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        d = {}\n",
    "        def helper2(circle):\n",
    "            x, y, r = circle\n",
    "            for i in range(x-r,x+r+1):\n",
    "                ymin = y-int((r**2-(i-x)**2)**0.5)\n",
    "                ymax = y+int((r**2-(i-x)**2)**0.5)\n",
    "                if i not in d:\n",
    "                    d[i] = [[ymin,ymax]]\n",
    "                else:\n",
    "                    d[i].append([ymin,ymax])\n",
    "                \n",
    "            return\n",
    "        \n",
    "        \n",
    "        for circle in circles:\n",
    "            helper2(circle)\n",
    "            \n",
    "        #print(d)\n",
    "        res = 0\n",
    "        for k in d:\n",
    "            tres = set([])\n",
    "            for minn,maxx in d[k]:\n",
    "                for i in range(minn,maxx+1):\n",
    "                    tres.add(i)\n",
    "            res += len(tres)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        \n",
    "        data = {}\n",
    "        for x, y, r in circles:\n",
    "            for di in range(- r, r + 1):\n",
    "                dj = (r ** 2 - di ** 2) ** (1/2)\n",
    "                dj = math.floor(dj)\n",
    "\n",
    "                if (x + di) not in data:\n",
    "                    data[x + di] = []\n",
    "\n",
    "                data[x + di].append([y - dj, y + dj])\n",
    "\n",
    "        ans = 0\n",
    "        for idx, block_list in data.items():\n",
    "            block_list = sorted(block_list, key=lambda x: x[0])\n",
    "            # print(idx, block_list)\n",
    "        \n",
    "            last_x, last_y = block_list[0]\n",
    "            for x, y in block_list[1:]:\n",
    "                if x <= last_y:\n",
    "                    last_y = max(last_y, y)\n",
    "                else:\n",
    "                    # print(idx, last_x, last_y)\n",
    "                    ans += (last_y - last_x + 1)\n",
    "                    last_x, last_y = x, y\n",
    "\n",
    "            # print(idx, last_x, last_y)\n",
    "            ans += (last_y - last_x + 1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        s = set()\n",
    "        for circle in circles:\n",
    "            x, y, r = circle[0], circle[1], circle[2]\n",
    "            for i in range(r + 1):\n",
    "                for j in range(r + 1):\n",
    "                    if i * i + j * j > r * r:\n",
    "                        continue\n",
    "                    s.add((x - i) * 1000 + y - j)\n",
    "                    s.add((x - i) * 1000 + y + j)\n",
    "                    s.add((x + i) * 1000 + y - j)\n",
    "                    s.add((x + i) * 1000 + y + j)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        y_min = lambda x, x1, y1, r1: math.ceil(-math.sqrt(r1*r1 - (x-x1)**2) + y1)\n",
    "        y_max = lambda x, x1, y1, r1: math.floor(math.sqrt(r1*r1 - (x-x1)**2) + y1)\n",
    "\n",
    "        ans = 0\n",
    "        x2yrange = defaultdict(list)\n",
    "        minX = min((x1-r1) for x1, y1, r1 in circles)\n",
    "        maxX = max((x1+r1) for x1, y1, r1 in circles)\n",
    "        for x in range(minX, maxX+1):\n",
    "            for (x1, y1, r1) in circles:\n",
    "                if x < x1 - r1 or x > r1 + x1:\n",
    "                    continue\n",
    "                y_min_ = y_min(x, x1, y1, r1)\n",
    "                y_max_ = y_max(x, x1, y1, r1)\n",
    "                x2yrange[x].append([y_min_, y_max_])\n",
    "        \n",
    "        for x, ys in x2yrange.items():\n",
    "            if len(ys) == 1:\n",
    "                ans += ys[0][1] - ys[0][0] + 1\n",
    "            elif len(ys) > 1:\n",
    "                ys.sort()\n",
    "                rs = [ys[0]]\n",
    "                for i in range(1, len(ys)):\n",
    "                    if ys[i][0] <= rs[-1][1]:\n",
    "                        rs[-1][1] = max(ys[i][1], rs[-1][1])\n",
    "                    else:\n",
    "                        rs.append(ys[i])\n",
    "                ans += sum(i[1] - i[0] + 1 for i in rs)\n",
    "\n",
    "        return ans\n",
    "                      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        s = set()\n",
    "        for circle in circles:\n",
    "            x,y,r = circle[0],circle[1],circle[2]\n",
    "            x_l,x_u = x-r,x+r\n",
    "            y_l,y_u = y-r,y+r\n",
    "            for i in range(x_l,x_u+1):\n",
    "                for j in range(y_l,y_u+1):\n",
    "                    if (i-x)**2 + (j-y)**2 <= r**2:\n",
    "                        s.add((i+1)*401 + j)\n",
    "                        \n",
    "        return len(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        s = set()\n",
    "        for x, y, r in circles:\n",
    "            for x_ in range(x - r, x + r + 1):\n",
    "                for y_ in range(y - r, y + r + 1):\n",
    "                    if x_ * 201 + y_ in s:\n",
    "                        continue\n",
    "                    elif (x_ - x) ** 2 + (y_ - y) ** 2 <= r ** 2:\n",
    "                        s.add(x_ * 201 + y_)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        # 把每个圆内的点找到然后做一个set，看长度就行\n",
    "        res = set()\n",
    "        cnt = 0\n",
    "        for i in circles:\n",
    "            x,y,r = i\n",
    "            for i in range(x -r,x+r+1):\n",
    "                for j in range(y-r,y+r+1):\n",
    "                    if (x-i)*(x-i)+(y-j)*(y-j)<=r*r:\n",
    "                        res.add(i*500+j) \n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        s1 = set()\n",
    "        for x, y, r in circles:\n",
    "            for dx in range(r+1):\n",
    "                for dy in range(r+1):\n",
    "                    if dx * dx + dy * dy <= r * r:\n",
    "                        s1 |= {(x - dx, y - dy), (x - dx, y + dy), (x + dx, y - dy), (x + dx, y + dy)}\n",
    "        return len(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for x, y, r in circles:\n",
    "            for dx, dy in product(range(r+1), range(r+1)):\n",
    "                if dx*dx+dy*dy<=r*r:\n",
    "                    res |= {(x+dx, y+dy), (x-dx, y+dy), (x+dx, y-dy), (x-dx, y-dy)}\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        ans = set()\n",
    "        for x, y, r in circles:\n",
    "            for x0 in range(r+1):\n",
    "                for y0 in range(r+1):\n",
    "                    if x0**2 + y0**2 <= r**2: \n",
    "                        ans.update({(x+x0, y+y0), (x+x0, y-y0), (x-x0, y+y0), (x-x0, y-y0)})\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for x, y, r in circles:\n",
    "            for dx in range(r + 1):\n",
    "                for dy in range(r + 1):\n",
    "                    if dx * dx + dy * dy <= r * r:\n",
    "                        res |= {(x + dx, y + dy), (x - dx, y + dy), (x + dx, y - dy), (x - dx, y - dy)}\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for x, y, r in circles:\n",
    "            for dx, dy in product(range(r + 1), range(r + 1)):\n",
    "                if dx * dx + dy * dy <= r * r:\n",
    "                    res |= {(x + dx, y + dy), (x - dx, y + dy), (x + dx, y - dy), (x - dx, y - dy)}\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        points = set()\n",
    "        for x, y, r in circles:\n",
    "            for i in range(-r, r + 1):\n",
    "                for j in range(-r, r + 1):\n",
    "                    if i ** 2 + j ** 2 <= r ** 2:\n",
    "                        points.add((x + i, y + j))\n",
    "        return len(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        Dict = {}\n",
    "        count = 0\n",
    "        for x, y, r in circles:\n",
    "            minx, miny = x-r, y-r\n",
    "            maxx, maxy = x+r, y+r\n",
    "            for px in range(minx, maxx+1):\n",
    "                for py in range(miny, maxy+1):\n",
    "                    s = str(px) +\",\" +str(py)\n",
    "                    if (px-x)**2 + (py-y)**2 <= r**2 and not Dict.get(s):\n",
    "                        Dict[s] = 1\n",
    "                        count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        def inCircle(x0, y0, r, x, y):\n",
    "            return (x - x0) ** 2 + (y - y0) ** 2 <= r ** 2\n",
    "        \n",
    "        ans = set()\n",
    "        for x, y, r in circles:\n",
    "            for i in range(x - r, x + r + 1):\n",
    "                for j in range(y - r, y + r + 1):\n",
    "                    if inCircle(x, y, r, i, j):\n",
    "                        ans.add((i, j))\n",
    "        \n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "            \n",
    "        \"\"\"\n",
    "        seen = set()        \n",
    "        circles.sort(key=lambda x : -x[2])\n",
    "\n",
    "        for xi,yi,ri  in circles:\n",
    "            for x in range(xi-ri,xi+ri+1):\n",
    "                for y in range(yi-ri,yi+ri+1):\n",
    "                    if (x-xi)*(x-xi) + (y-yi)*(y-yi)<=ri*ri:\n",
    "                        seen.add(x*1000+y)\n",
    "        return len(seen)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        # x^2 + y^2 = r^2\n",
    "\n",
    "        hashmap = dict()\n",
    "\n",
    "        for cx, cy, r in circles:\n",
    "            for x in range(cx-r, cx+r+1):\n",
    "                for y in range(cy-r, cy+r+1):\n",
    "                    if (x-cx)**2+(y-cy)**2 <= r**2 and not (x, y) in hashmap:\n",
    "                        hashmap[(x, y)] = 1\n",
    "        \n",
    "        return len(hashmap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "            \n",
    "        \"\"\"\n",
    "        seen = set()        \n",
    "        # circles.sort(key=lambda x : -x[2])\n",
    "\n",
    "        for xi,yi,ri  in circles:\n",
    "            for x in range(xi-ri,xi+ri+1):\n",
    "                for y in range(yi-ri,yi+ri+1):\n",
    "                    if (x-xi)*(x-xi) + (y-yi)*(y-yi)<=ri*ri:\n",
    "                        seen.add(x*1000+y)\n",
    "        return len(seen)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "            \n",
    "        \"\"\"\n",
    "        seen = set()        \n",
    "        for xi,yi,ri  in circles:\n",
    "            for x in range(xi-ri,xi+ri+1):\n",
    "                for y in range(yi-ri,yi+ri+1):\n",
    "                    if (x-xi)**2 + (y-yi)**2<=ri**2:\n",
    "                        seen.add(x*1000+y)\n",
    "        return len(seen)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        result = set()\n",
    "        for i in circles:\n",
    "            r = i[2]\n",
    "            for x in range(-r,r+1):\n",
    "                for y in range(-floor(sqrt(r*r-x*x)),floor(sqrt(r*r-x*x))+1):\n",
    "                    result.add(\"{}\".format((i[0]+x,i[1]+y)))\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        vis = set()\n",
    "        circles.sort(key=lambda c: c[-1])\n",
    "        for xc, yc, r in circles:\n",
    "            for x in range(xc-r, xc+r+1):\n",
    "                for y in range(yc-r, yc+r+1):\n",
    "                    if (x, y) not in vis and (x-xc)*(x-xc) + (y-yc)*(y-yc) <= r*r:\n",
    "                        vis.add((x, y))\n",
    "        return len(vis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        n = len(circles)\n",
    "        visited = set()\n",
    "\n",
    "        for x, y, r in circles:\n",
    "            for i in range(x - r, x + r + 1):\n",
    "                for j in range(y - r, y + r + 1):\n",
    "                    if (i * 1000 + j) not in visited and (i - x) * (i - x) + (j - y) * (j - y) <= r * r:\n",
    "                        visited.add(i * 1000 + j)\n",
    "\n",
    "        return len(visited)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        v=set()\n",
    "        for i in circles:\n",
    "            for j in range(i[0]-i[2],i[0]+i[2]+1):\n",
    "                for k in range(i[1]-i[2],i[1]+i[2]+1):\n",
    "                    if (j-i[0])**2+(k-i[1])**2<=i[2]**2:\n",
    "                        v.add((j,k))\n",
    "        return len(list(v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        dic = set()\n",
    "        for x, y, r in circles:\n",
    "            for i in range(-r, r + 1):\n",
    "                for j in range(-r, r + 1):\n",
    "                    if i * i + j * j <= r * r:\n",
    "                        dic.add((x + i, y + j))\n",
    "        return len(dic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        \n",
    "        res = set()\n",
    "        for circle in circles:\n",
    "            x, y = circle[0], circle[1] # 3， 4\n",
    "            left, right, up, down = x - circle[2], x + circle[2], y + circle[2], y - circle[2]\n",
    "            for i in range(down, up + 1): #3, 5  \n",
    "                for j in range(left, right + 1): #2, 4\n",
    "                    if (j,i) in res:\n",
    "                        continue\n",
    "                    if (i - y) ** 2 + (j - x) ** 2 <= circle[2] ** 2:\n",
    "                        res.add((j,i))\n",
    "            \n",
    "        print(res)\n",
    "        return len(res)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        save_dict = {}\n",
    "        for x, y, r in circles:\n",
    "            for new_x, new_y in [[x-r, y], [x+r, y], [x, y-r], [x, y+r]]:\n",
    "                if (new_x, new_y) not in save_dict:\n",
    "                    save_dict[(new_x, new_y)] = 1\n",
    "            save_dict = self.cal_inner_point(x, y, r, save_dict)\n",
    "        return len(save_dict)\n",
    "\n",
    "    def cal_inner_point(self, x, y, r, save_dict):\n",
    "        new_r = r - 1\n",
    "        threshold = r ** 2\n",
    "        for new_x in range(x-new_r, x+new_r+1):\n",
    "            for new_y in range(y-new_r, y+new_r+1):\n",
    "                dis = (new_x - x) ** 2 + (new_y - y) ** 2\n",
    "                if (new_x, new_y) not in save_dict and dis <= threshold:\n",
    "                    save_dict[(new_x, new_y)] = 1\n",
    "        return save_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for x,y,r in circles:\n",
    "            for dx,dy in product(range(r+1),range(r+1)):\n",
    "                if dx*dx+dy*dy<=r*r:\n",
    "                    res |={(x+dx,y+dy),(x-dx,y+dy),(x-dx,y-dy),(x+dx,y-dy)}\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        def distance(x,y):\n",
    "            return pow((x[0]-y[0])*(x[0]-y[0])+(x[1]-y[1])*(x[1]-y[1]),0.5)\n",
    "        ans = set()\n",
    "        for circle in circles:\n",
    "            for i in range(circle[0]-circle[2],circle[0]+circle[2]+1):\n",
    "                for j in range(circle[1]-circle[2],circle[1]+circle[2]+1):\n",
    "                    if distance([i,j],[circle[0],circle[1]])<=circle[2] and (i,j) not in ans:\n",
    "                        ans.add((i,j))\n",
    "        print(ans)\n",
    "        return len(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: list[list[int]]) -> int:\n",
    "\n",
    "        points = set()\n",
    "        for circle in circles:\n",
    "            center = (circle[0], circle[1])\n",
    "            radius = circle[2]\n",
    "\n",
    "            tmp_points = []\n",
    "            radius_mul = radius ** 2\n",
    "            for i in range(radius + 1):\n",
    "                for j in range(radius + 1):\n",
    "                    if i ** 2 + j ** 2 <= radius_mul:\n",
    "                        tmp_points.append((i, j))\n",
    "\n",
    "            for p in tmp_points:\n",
    "                points.add((p[0] + center[0], p[1] + center[1]))\n",
    "                points.add((-1 * p[0] + center[0], p[1] + center[1]))\n",
    "                points.add((p[0] + center[0], -1 * p[1] + center[1]))\n",
    "                points.add((-1 * p[0] + center[0], -1 * p[1] + center[1]))\n",
    "\n",
    "        return len(points)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        output = []\n",
    "        d = defaultdict(int)\n",
    "        for circle in circles:\n",
    "            for i in range(circle[0]-circle[2], circle[0]+circle[2]+1):\n",
    "                for j in range(circle[1]-circle[2], circle[1]+circle[2]+1):\n",
    "                    if pow((i-circle[0]), 2) + pow((j-circle[1]), 2) <= pow(circle[2], 2):\n",
    "                            d[(i,j)] = 1\n",
    "        return len(list(d.keys()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def collectPoints(self, c, r: int) -> List[int]:\n",
    "        if str(c[0]) + ',' + str(c[1]) not in self.res:\n",
    "            self.res.add(str(c[0]) + ',' + str(c[1]))\n",
    "        # pointsList = [[c[0],c[1]]]\n",
    "        for _r in range(1, r+1):\n",
    "            # pointsList += [[c[0], _r+c[1]], [c[0],-_r+c[1]], [c[0]+_r, c[1]], [c[0]+-_r, c[1]]]\n",
    "            for _p in [[c[0], _r+c[1]], [c[0],-_r+c[1]], [c[0]+_r, c[1]], [c[0]+-_r, c[1]]]:\n",
    "                if str(_p[0]) + ',' + str(_p[1]) in self.res:\n",
    "                    continue\n",
    "                else:\n",
    "                    self.res.add(str(_p[0]) + ',' + str(_p[1]))\n",
    "        # pointsList += [[0, -_r] for _r in range(1, r+1)]\n",
    "        # pointsList += [[_r, 0] for _r in range(1, r+1)]\n",
    "        # pointsList += [[-_r, 0] for _r in range(1, r+1)]\n",
    "        for i in range(1, r+1):\n",
    "            # y = int(math.sqrt((r-i)*(r+i)))\n",
    "            y = self.sqrt_dict[str(r) + str(i)]\n",
    "            for _y in range(1, y+1):\n",
    "                # pointsList += [[c[0]+i, c[1]+_y], [c[0]+-i, c[1]+_y], [c[0]+i, c[1]+-_y], [c[0]+-i, c[1]+-_y]]\n",
    "                for _p in [[c[0]+i, c[1]+_y], [c[0]+-i, c[1]+_y], [c[0]+i, c[1]+-_y], [c[0]+-i, c[1]+-_y]]:\n",
    "                    if str(_p[0]) + ',' + str(_p[1]) not in self.res:\n",
    "                        self.res.add(str(_p[0]) + ',' + str(_p[1]))\n",
    "        return\n",
    "            # pointsList += [[-i, _y] for _y in range(1, y+1)]\n",
    "            # pointsList += [[i, -_y] for _y in range(1, y+1)]\n",
    "            # pointsList += [[-i, -_y] for _y in range(1, y+1)]\n",
    "        # print(pointsList)\n",
    "        # return pointsList\n",
    "    \n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        self.res = set()\n",
    "        self.sqrt_dict = {}\n",
    "        for r in range(1, 101):\n",
    "            for i in range(1, r+1):\n",
    "                self.sqrt_dict[str(r) + str(i)] = int(math.sqrt((r-i)*(r+i)))\n",
    "        for circle in circles:\n",
    "            _pointsList = self.collectPoints(circle, circle[2])\n",
    "            # for _point in _pointsList:\n",
    "            #     # temp_point = [_point[0] + circle[0], _point[1] + circle[1]]\n",
    "            #     if _point in self.res:\n",
    "            #         continue\n",
    "            #     else:\n",
    "            #         self.res.append(_point)\n",
    "        return len(self.res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        hashmap = dict()\n",
    "\n",
    "        for cx, cy, r in circles:\n",
    "            for x in range(cx-r, cx+r+1):\n",
    "                for y in range(cy-r, cy+r+1):\n",
    "                    if (x-cx)**2+(y-cy)**2 <= r**2 and not (x, y) in hashmap:\n",
    "                        hashmap[(x, y)] = 1\n",
    "        \n",
    "        return len(hashmap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        # x^2 + y^2 = r^2\n",
    "\n",
    "        hashmap = dict()\n",
    "\n",
    "        for cx, cy, r in circles:\n",
    "            for x in range(cx-r, cx+r+1):\n",
    "                for y in range(cy-r, cy+r+1):\n",
    "                    if (x-cx)**2+(y-cy)**2 <= r**2 and not (x, y) in hashmap:\n",
    "                        hashmap[(x, y)] = 1\n",
    "        \n",
    "        return len(hashmap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for circle in circles:\n",
    "            # four_point = [[circle[0] + circle[2], circles[1]], [circle[0] - circle[2], circles[1]], [circle[0], circles[1] + circle[2]],[circle[0], circles[1] - circle[2]]]\n",
    "            # for point in four_point:\n",
    "            #     res.add(point[0] * 201 + point[1])\n",
    "            for i in range(circle[0] - circle[2], circle[0] + circle[2] + 1):\n",
    "                for j in range(circle[1] - circle[2], circle[1] + circle[2] + 1):\n",
    "                    if (i - circle[0]) ** 2 + (j - circle[1]) ** 2 <= circle[2] ** 2:\n",
    "                        res.add(i * 201 + j)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        circles = set(tuple(circle) for circle in circles)\n",
    "        \n",
    "        res = set()\n",
    "        \n",
    "        for ox, oy, r in circles:\n",
    "            for x in range(ox - r, ox + r + 1):\n",
    "                for y in range(oy - r, oy + r + 1):\n",
    "                    if ((x - ox) * (x - ox) +\n",
    "                        (y - oy) * (y - oy) <= r * r):\n",
    "                        res.add((x, y))\n",
    "                        \n",
    "        return len(res)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        check=set()\n",
    "        def cal(x,y):\n",
    "            return ((x-x0)**2+(y-y0)**2)**0.5<=r\n",
    "        for x0,y0,r in circles:\n",
    "            for i in range(x0-r,x0+r+1):\n",
    "                for j in range(y0-r,y0+r+1):\n",
    "                    if cal(i,j):\n",
    "                        check.add((i,j))\n",
    "        return len(check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        ret = set()\n",
    "        for x, y, r in circles:\n",
    "            for i in range(x - r, x + r + 1):\n",
    "                for j in range(y - r, y + r + 1):\n",
    "                    if (i, j) not in ret and (x - i) ** 2 + (y - j) ** 2 <= r ** 2 :\n",
    "                        ret.add((i, j))\n",
    "        return len(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        def find(x: int, y: int, r: int) -> None:\n",
    "            ans = 1\n",
    "            left = x - r\n",
    "            right = x + r + 1\n",
    "            h1 = h2 = y\n",
    "            while left < x:\n",
    "                for i in range(left, right):\n",
    "                    s.add((i, h1))\n",
    "                    s.add((i, h2))\n",
    "                h1 += 1\n",
    "                h2 -= 1\n",
    "                left = x - int(sqrt(r ** 2 - (y - h1) ** 2))\n",
    "                right = x * 2 - left + 1\n",
    "            s.add((x, y + r))\n",
    "            s.add((x, y - r))\n",
    "        s = set()\n",
    "        for x, y, r in circles:\n",
    "            find(x, y, r)\n",
    "        return len(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countLatticePoints(self, circles: List[List[int]]) -> int:\n",
    "        points_set = set()\n",
    "        res = 0\n",
    "        for x, y, r in circles:\n",
    "            for i in range(x - r, x + r + 1):\n",
    "                for j in range(y - r, y + r + 1):\n",
    "                    if (i, j) not in points_set and (i - x) ** 2 + (j - y) ** 2 <= r ** 2:\n",
    "                        res += 1\n",
    "                        points_set.add((i, j))\n",
    "        return res\n",
    "                        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
